\documentclass[a4paper,10pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage[pdftex]{graphicx}

\begin{document}
\title{\textbf{Sistemas Operativos}\\ Trabajo Práctico 2\\ }
\author{45129 - Gou Xinwei \\ 45390 - Oybin Pablo Nahuel \\ 46069 - Sessa Carlos}
\date{}
\maketitle

\begin{abstract}
\begin{center}
    Multitasker.
\end{center}
\end{abstract}

\section{Objetivos}
Realizar un programa que conmute diferentes procesos, asignándoles a cada uno
un tiempo de ejecución. El multitasker no corre sobre ningún Sistema Operativo,
se ubica en memoria utilizando el bootloader GRUB.

\section{Consigna}
El trabajo consta de la realización de un Multitasker, cuyo objetivo es asignar
tiempo de ejecución a diferentes procesos en memoria. El sistema deberá ser
implementado para plataformas Intel de 32 bits, utilizando el procesador en
modo protegido. El multitasker debe ser preemptivo, es decir, cualquier tarea
puede ser desalojada del microprocesador. El encargado de administrar el CPU
es el scheduler el cual tomará como base de tiempo la interrupción de hardware
INT8 correspondiente al timer tick, para realizar la asignacin de tiempo (time
slot).

\section{Introducción}
En este escrito se explicarán las decisiones tomadas durante el desarrollo del
trabajo. Tener en cuenta que no se explicarán todas las funcionalidades, ya que
algunas fueron el fruto de lo realizado en la materia Arquitectura de las
computadoras. Se entrega también el informe correspondiente a esa
materia.

En la primera sección \textbf{Procesos} se da a conocer cómo se modeló un
proceso. Luego se comenta acerca del \textbf{Contexto de Tareas} para
explicar lo realizado con el \textbf{Scheduler} y sus algoritmos de desalojo.
En \textbf{Administrador de Memoria} se explica cómo se hace el manejo de
la memoria.
Para probar el correcto funcionamiento tuvimos que crear nuevas aplicaciones
que se explicarán en la sección \textbf{Programas de prueba}.
Por último se ofrece una sección de \textbf{Problemas encontrados} seguida
de \textbf{Posibles extensiones}.

\section{Implementación}

\subsection{Procesos}

\begin{verbatim}
typedef struct PROCESS
{
    int pid;
    char name [MAX_PROCESS_NAME];
    int priority;
    int tty;
    int foreground;
    int lastCalled;
    int sleep;
    int blocked;
    int parent;
    int ESP;
    int free;
    int stackstart;
    int stacksize;
    int heap_page;
    int stack_page;
    int next_free;
} PROCESS;
\end{verbatim}
\subsubsection{int pid}
En esta variable, se guarda el número de proceso. Es la forma de identificar un
proceso unívocamente.

\subsubsection{char name $[MAX\_PROCESS\_NAME]$}
Nombre del proceso. Sirve para mostrarlo en pantalla por aplicaciones como top.

\subsubsection{int priority}
Esta variable es la prioridad con la que se va a correr el proceso.  Es un
entero entre 0 y 4, siendo 0 la máxima prioridad. Sirve siempre y cuando
el scheduler esté usando un algoritmo de desalojo con prioridad.

\subsubsection{int tty}
La variable $tty$ indica el número de terminal desde donde se ejecutó el
proceso. Se usa cuando el proceso quiere imprimir en pantalla.

\subsubsection{int foreground}
Si este flag está encendido la terminal en la que ejecuta el proceso espera
hasta que termine.  Si está en cero, corriendo como $background$, la terminal
no queda bloqueada, sino que sigue aceptando comandos.

\subsubsection{int lastCalled}
Es una varible interna del sistema, utilizada por el scheduler.

\subsubsection{int sleep}
Si tiene un valor mayor a 0, el proceso no está durmiendo y puede ser
ejecutado.

\subsubsection{int blocked}
Si esta variable tiene un valor distinto de 0, entonces el proceso se
encuentra bloqueado y no puede ser ejecutado.

\subsubsection{int parent}
Es de suma utilidad en el caso de que se mate a un proceso que ha creado
hijos y esto se debe a que en caso de ejecutar el comando kill
sobre un proceso, también hay que terminar los procesos hijos del mismo.

\subsubsection{int ESP}
Aquí se guarda el valor del registro \texttt{esp}.

\subsubsection{int free}
Esta variable denota si la posición en el arreglo de procesos puede
ser utilizado por algún proceso o si está ocupado por un proceso en
ejecución.

\subsubsection{int stackstart}
Esta variable guarda el valor de donde empieza la zona de stack.

\subsubsection{int stacksize}
Es el tamaño del stack.

\subsubsection{int heap\_page}
Acá almacenamos la página utilizada para el heap del proceso.

\subsubsection{int stack\_page}
Igual que el heap, pero con el stack.

\subsubsection{int next\_free}
Como cada proceso cuenta con una página para heap, en esta variable se
guarda el valor de la proxima zona de memoria disponible.

\subsection{Contexto de Tareas}
Al intercambiar constantemente tareas, es necesario guardar el estado
actual de los registros del procesador.
Para resguardar los valores de los registros utilizamos la función
\emph{pushad}, que lo que hace es un \emph{push} de los registros tal
y cual están hacia el stack.

También es necesario guardar en algún lugar el valor de ESP para cuando
tengamos que retomar la tarea sepamos donde estaba el puntero a la zona
de stack, y asi podamos recuperar el estado de los registros, y para eso
utilizamos la función \emph{SaveESP}.

Para recuperar una tarea, recuperamos el valor del puntero al stack mediante
la función \emph{LoadESP}.  Con ese valor, se utiliza la función \emph{popad}
que levanta del stack el estado de los registros.

\subsection{Scheduler}
Para realizar la conmutación de tareas, el scheduler selecciona en base a
distintos algoritmos el próximo proceso a ejecutar.
Para cambiar el algoritmo de scheduling usar el comando $sched$.

\subsubsection{Scheduler con prioridad}
Se determina un número entero para cada proceso, en base a su prioridad
y a cuantas veces se ejecutó repetidamente.
Ese número entero se le asigna a cada proceso y el que obtenga el valor
más alto es el que se ejecuta.

\subsubsection{Lotería}
El proceso de selección es similar al mencionado anteriormente con la
diferencia que la suerte entra en juego. A cada proceso se le asigna
un ticket, determinado por la función random, y se utiliza para
calcular el número entero para la selección del próximo proceso.

\subsection{Administrador de Memoria}
Este módulo sirve para poder controlar que los procesos no pueda escribir
en las zonas de memoria que no le corresponden, que no puedan arruinar su
propio stack o excederse en la cantidad de memoria alocada.
Para ello, existen funciones para alocar memoria para el proceso usuario
como también funciones para que el kernel aloque espacio para el stack.
Cuando el scheduler asigna una tarea, se verifica el tamaño de stack restante 
del proceso, comparando la posición del Stack Pointer con la posición de 
comienzo de Stack del proceso. Si el tamaño restante es menor a cierto 
parámetro establecido, se otorgan más páginas para la memoria.
Como las páginas para el Stack tienen que ser contigüas, el método para
otorgar más páginas es el siguiente:
Se busca la última página ocupada por algún proceso, y se establece la
siguiente como la nueva primer página de Stack. Esa página se va a dejar libre,
ya que es el nuevo espacio que va a tener el proceso para crecer en Stack.
A partir de la siguiente página se copia el contenido de las viejas páginas
de Stack.
Para ello, previamente se habilitan éstas páginas seteando el bit de Present.
Por último se actualizan los valores del Stack Pointer(ESP), y recursivamente 
se actualizan los valores del registro EBP, que estaban previamente alojados 
en el Stack.
Por último, se deshabilitan las páginas que el proceso utilizaba previamente 
para Stack y se marcan en desuso.

Para saber que páginas están siendo utilizados por procesos, hay un arreglo 
donde cada índice indica una entrada en la tabla de páginas y el valor es el 
PID del proceso que la está utilizando, en caso de que sea una página 
utilizada para Stack. En caso de que la página este siendo utilizada para heap, 
el valor es el PID multiplicado por 100 y negado. Ésta diferencia la hacemos porque 
los procesos no poseen páginas propias de heap pero sí de stack, entonces al momento 
del cambio de tareas, sacamos el bit de present a las páginas de stack pero no a las de 
heap. Sin embargo, cuando se destruye un proceso, tenemos que tener forma de identificar 
todas las páginas utlizadas por ese proceso para deshabilitarlas y marcarlas como libres.

\subsection{Alocación}
La función wMalloc, es similar al Malloc, con la diferencia de que si el tamaño 
requerido no entra en las páginas asignadas al proceso, se asignan más páginas 
para el heap.

\subsection{Variables globales del Sistema Operativo}
La lectura y escritura de variables globales del SO por procesos de usuario 
debe ser realizada mediante system calls. En nuestra implementación, a modo de 
ejemplo, realizamos esto para la variable CurrentPID (el PID del proceso qe se 
está ejecutando actualmente). Esto se realiza mediante la INT 80, con eax seteada 
en 10 u 11, depende se es lectura o escritura, llamando a las funciones getVal() o setVal().


\subsection{Programas de prueba}
En esta sección se dará a conocer los comandos que no se encontraban en el
trabajo práctico de Arquitectura de las computadoras.

\subsubsection{Top}
El comando top le indica al usuario los procesos en ejecución.
Le informa su $pid$, en qué terminal se están ejecutando, su nombre y el
porcentaje de la cpu que está utilizando.
La cantidad de cpu que utiliza cada proceso depende del tipo de scheduling
utilizado. Si es scheduling con prioridad podrían verse procesos con más
cpu que otros, mientras que de usar scheduling sin prioridad todos deberían
usar prácticamente la misma cantidad.

\subsubsection{Counter}
Éste proceso realiza varios wMallocs y muestra como se van asignando más páginas 
para el heap.

\subsubsection{Nice}
El comando nice permite cambiar la prioridad de un proceso.
Debe llamarse con nice pid y luego pregunta la prioridad a elegir.

\subsubsection{Kill}
El comando kill $pid$ mata al proceso con un número de proceso $pid$.

\subsubsection{FactOK}
Proceso que llama a una función recursiva que tiene una variable local de gran tamaño, 
luego realiza un Sleep(), entonces cuando el scheduler realiza el cambio de tareas, le 
asigna más páginas para el stack y muestra éste resultado en pantalla.


\subsubsection{FactNotOK}
Éste proceso muestra la vulnerabilidad del SO que sólo verifica el tamaño del 
Stack en el cambio de tareas, como se pide más espacio del que el proceso tiene 
inicialmente, genera una excepción.




\section{Problemas encontrados}
\subsection{Debuggear}
El hecho de tener funciones en assembler dificulta mucho el debugging
de la aplicación. Nos ayudó mucho tener la directiva make debug que
permite usar gdb en las funciones de C del sistema operativo.
\subsection{Stack}
La verificación del tamaño del stack requerido por el proceso se realiza al momento
de que el scheduler cambia a la tarea. Por lo tanto si durante la ejecución del proceso,
se excede del tamaño del stack puede ser que intente acceder a una página que no le pertenece
generando una excepción, o escribiendo en una zona de otro proceso.


\section{Posibles extensiones}
\subsection{IPCs}
Creemos que todo sistema operativo debe contar con algún IPC.
Aprovechando que todas las funciones de C hechas tienen el mismo
prototipo que las originales, podría intentarse migrar el tp01.

\subsection{Correcto manejo de restart y shutdown}
En el trabajo de arquitecturas se había implementado funciones
shutdown, restart, y tf (triple-fault). Algunos usaban algunos
hacks como generar una excepción y así reiniciar la pc.
Como el sistema atrapa excepciones, algunas de estas funcionalidades
quedaron invalidadas.

\subsection{Módulo de debuggeo de assembler}
Para continuar con el desarrollo del sistema operativo sería conveniente
generar un módulo de debuggeo de assembler. Con esta herramienta se podría
mejorar mucho la performance del trabajo analizando qué pasa cuando se
realizan llamadas del sistema.

\subsection{Stack}
Una mejora podría ser verificar el tamaño del stack en el handler de las excepciones
de tal forma que se otorgue más páginas para la memoria cuando el proceso las necesite
y no esperar a que el scheduler realice el cambio de tareas.
Con nuestro método de asignación de nuevas páginas de stack, es posible que dejemos páginas
sin uso, cuando enrealidad podríamos haberlas utilizado como nuevas páginas de stack. Ésto
se debe a que nosotros elegimos como nuevas páginas la siguiente a la última utilizada por un proceso.
Si el proceso que necesita más stack es el último, en lugar de utilizar las viejas páginas como espacio
para las nuevas, éstas se saltean quedando libres.

\subsection{Malloc}
Una mejora para la funcion de alocación sería realizarla mediante un system call. Ésto es necesario 
ya que en ésta función se leen y escriben variables globales del sistema operativo y se decide sobre 
la utlización de memoria.

\subsection{Variables globales del Sistema Operativo}
Dependiendo el parametro enviado a las funciones getVal() o setVal(), se pueden leer y/o escribir 
distintas variables globales del SO. Ésta implementado únicamente para la variable CurrentPID, pero 
es extensible para cualquier variable del SO, ya que en las funciones se verifica el parámetro recibido 
y se decide de dónde leer o dónde escribir.




\begin{thebibliography}{}

\bibitem[Keith Haviland, 1999]
- Keith Haviland, Dina Gray, Ben Salama, \emph{UNIX System Programming Second Edition},
Addison-Wesley, 1999.

\bibitem[Blaise Barney, 2009]
- Blaise Barney, \emph{POSIX Threads Programming},
https://computing.llnl.gov/tutorials/pthreads/,
Lawrence Livermore National Laboratory, 2009.



\end{thebibliography}
\end{document}
